from itertools import accumulate

# 求子数组 a[left..right] 的最大子数组和
def maxSum(a: list[int], left: int, right: int) -> int:
    if left == right: return a[left] # 仅一个元素时直接返回

    # 第1步：划分
    mid = left + (right - left) // 2

    # 第2步：求解子问题
    s1 = maxSum(a, left, mid)      # 递归求左子数组
    s2 = maxSum(a, mid + 1, right) # 递归求右子数组

    # 求中间段的和
    maxleft = max(accumulate(range(mid, left - 1, -1), lambda s, i: s + a[i], initial=0))
    maxright = max(accumulate(range(mid + 1, right + 1), lambda s, i: s + a[i], initial=0))

    # 第3步：合并解并返回
    max_s = max(s1, s2);
    if maxleft + maxright > 0: # 思考：为何要加这句判断？
        max_s = max(max_s, maxleft + maxright);

    return max_s;

# main
a = [ -20, 10, -30, 40, -10, 20, 10, -50, 40 ]
sum = maxSum(a, 0, len(a) - 1)
print('最大子数组和为:', sum)
